package 剑指offer;

import java.util.HashSet;
import java.util.Set;

public class p3数组中重复的数字 {

    public int findRepeatNumber(int[] nums) {
        //原地哈希
        for (int i = 0; i <nums.length; i++) {
            while (nums[i] != i) {
                //下标对应元素的值 不等于 下标，就要给这个元素归位
                if (nums[nums[i]] != nums[i]) {
                    //元素自己位置的值 不等于 当前下标元素的值，就可以进行互换
                    int tmp=nums[nums[i]];
                    nums[nums[i]]=nums[i];
                    nums[i]=tmp;
                }else {
                    //元素自己位置的值 等于 当前下标元素的值，那么这个元素就是重复的
                    return nums[i];
                }
            }
        }
        return -1;
    }

    public int findRepeatNumber1(int[] nums) {
        //创建哈希表HashSet,利用它add()方法不能添加重复元素的特点
        Set<Integer> set=new HashSet<>();

        for (int x:nums) {
            if (!set.add(x)){
                return x;
            }
        }
        return -1;

    }
}
